package done.normal_101_200;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 103. Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层次遍历
 * <p>
 * 给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 * <p>
 * 例如：
 * 给定二叉树 [3,9,20,null,null,15,7],
 * <p>
 * 3              ------>  第一层
 * / \
 * 9  20            <------  第二层
 * /  \
 * 15   7          ------>  第三层
 * 返回锯齿形层次遍历如下：
 * [[3],
 * [20,9],
 * [15,7]]
 */
@SuppressWarnings("all")
public class BinaryTreeZigzagLevelOrderTraversal {

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList();
        // 190510 first
        return list;
    }

    @Test
    public void test() {
        TreeNode root = new TreeNode(3,
                9, new TreeNode(20,
                15, 7));
        info(zigzagLevelOrder(root));
    }
}











































/*
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> list = new ArrayList();
    add(list,root,0);
    return list;
}

private void add(List<List<Integer>> list, TreeNode root, int index){
    if (root == null)
        return;

    if (list.size() > index) {
        if (index%2 == 0)
            list.get(index).add(root.val);//队列尾
        else
            list.get(index).add(0, root.val);//队列头
    } else {
        list.add(new ArrayList(){{
            add(root.val);
        }});
    }

    add(list, root.left, index + 1);

    add(list, root.right, index + 1);
}
*/
